package net.dodoman.suanfa;

public class MaoPao {
	// 最普通的冒泡算法，需要比较(n-1)*(n-1)次
	public static void test1() {
		int[] iArray = { 10, 5, 2, 3, 321, 76, 3221, 98, 86, 39 };
		int k = 0;
		int icount = 0;
		for (int j = 0; j < iArray.length - 1; j++) {
			for (int i = 0; i < iArray.length - 1; i++) {
				if (iArray[i] > iArray[i + 1]) {
					k = iArray[i];
					iArray[i] = iArray[i + 1];
					iArray[i + 1] = k;
				}
				icount++;
			}
		}
		System.out.println("共做比较次数： " + icount);
		for (int i = 0; i < iArray.length; i++) {
			System.out.print(" " + iArray[i]);
		}
	}

	// 稍微作了一下改进，加入一个布尔变量，当顺序已经排好后，就不用做额外的比较了
	public static void test2() {
		int[] iArray = { 10, 5, 2, 3, 321, 76, 3221, 98, 86, 39 };
		int k = 0;
		int icount = 0;
		boolean b = false;
		for (int j = 0; j < iArray.length - 1; j++) {
			b = false;
			for (int i = 0; i < iArray.length - 1; i++) {
				if (iArray[i] > iArray[i + 1]) {
					k = iArray[i];
					iArray[i] = iArray[i + 1];
					iArray[i + 1] = k;
					b = true;
				}
				icount++;
			}
			if (!b)
				break;
		}
		System.out.println("\r\n\r\n共做比较次数： " + icount);
		for (int i = 0; i < iArray.length; i++) {
			System.out.print(" " + iArray[i]);
		}
	}

	public static void main(String[] args) {
		test1();
		test2();
	}
}